Intelligent Transport Systems (ITS), as defined by Directive 2010/40/EU, are systems in which information and communication technologies are applied in the field of road transport, including infrastructure, vehicles and users, and in traffic management and mobility management, as well as for interfaces with other modes of transport (Article 4(1) of the ITS Directive). In this context, reliable vehicle-to-vehicle (V2V) and vehicle-to-infrastructure (V2I) communication is an essential element. Such communication is used for both real time exchange of safety messages between vehicles and with infrastructure to resolve potentially dangerous road situations as well as to exchange essential information to improve traffic. V2V/V2I communication is based on the IEEE 802.11p standard, which is an amendment to the IEEE 802.11 standards to add wireless access in vehicular environments within the designated ITS band of 5.85 to 5.925 GHz.
Security of any communication links within ITS is clearly fundamental to prevent unwanted, wrong or misleading information. Security is predominantly used to authenticate that messages are coming from trusted sources, and therefore the information they carry can be trusted as well. This can be done using asymmetrical keys where a sender signs a message using their secret private key and a recipient can verify that the signature and message are coming from that particular sender using the sender's known public key corresponding to the private key.
The most widely known and used type of public key cryptography is RSA, based on the asymmetric difficulty of multiplying two large prime numbers and factorising the resulting number without prior knowledge of its factors. The two large prime numbers forms the basis of a private key, as this provides the solution to the factorisation problem, while the product can form the basis of a public key, whose knowledge cannot be used to easily determine the two prime factors. Another type of public key cryptography is known as Elliptic Curve Cryptography (ECC), which has been proposed for use in ITS, the main reason being that ECC keys and signatures are of much shorter length while still providing the same level of security as much longer keys in alternative approaches such as RSA. This property minimizes overhead in communication taking into account that the signature and the public key needs to be communicated with each message. Both types of cryptography require large numbers to be multiplied together as part of the verification process.
An ECC scheme is determined by key length and the chosen underlying curve. Typical ITS key lengths considered are, for example, 256 bits, 384 bits or 512 bits. The NIST (P256, P384, P512) curves are also used in ITS predominantly, but other choices such as Brainpool curves may be used. In ECC, the main algorithm for signing messages and verifying the signatures is called the Elliptic Curve Digital Signature Algorithm (ECDSA).
In ITS V2V or V2I (which may be encompassed by the general term V2X, or vehicle to everything), cars are typically broadcasting safety messages at rates of tens of messages per second (e.g. 10-20 Hz). A particular car may be receiving messages from hundreds (e.g. 100-200) of other cars and therefore needs to receive and authenticate thousands of messages a second (e.g. 1000-2000). Therefore, the speed of authentication computations is an important parameter in ITS, as this will determine how many messages can be authenticated and used for safety or traffic management applications and how many other cars a particular car can trust and consider in road situations.
Authentication computations, for example using ECDSA, are based on computation of large numbers (e.g. 256-512 bits and beyond). Basic computations involve multiplications, additions and subtractions of large numbers. Most other operations (including division) are based on these three operations. Considering that both multiplication and subtraction (in general, of large numbers in particular) are based on addition, a fundamental point is that addition of large numbers is a major contributor to computation times in large number arithmetic operations.